"""
对链表值进行求和    wget -nc https://labfile.oss.aliyuncs.com/courses/1512/linked_list.py
挑战介绍
实现一个算法来对链表中结点的元素值进行求和。要求如下：

数字以相反的顺序存储在链表中，如数字 37 在链表中存储的方式是，第 1 个结点为数字 7 ，第 2 个结点为数字 3 。
求和是把两个链表的数字求和后，以相反的顺序存储在链表中。例如第一个链表的数字是 37，即输入为 7 -> 3，第二个链表输入为 2 -> 8，则输出链表为 9 -> 1 -> 1。
挑战内容
本次挑战中，你需要在 reverse.py 文件中补充函数 add_reverse 的空缺部分。

MyLinkedList 类继承“实现链表类”挑战中的 LinkedList 类。
MyLinkedList 类的 add_reverse 方法用于对链表数字进行求和，参数 first_list 用于指定传入的第一个链表，参数 second_list 用于指定传入的第二个链表，它返回一个链表。
如果传入链表中有 None，则返回 None。
"""
from linked_list import LinkedList, Node


class MyLinkedList(LinkedList):

    def add_reverse(self, first_list, second_list):
        # See constraints
        if first_list is None or second_list is None:
            return None
        head = self._add_reverse(first_list.head, second_list.head, 0)
        return MyLinkedList(head)

    def _add_reverse(self, first_node, second_node, carry):
        # Base case
        if first_node is None and second_node is None and not carry:
            return None

        # Recursive case
        value = carry
        value += first_node.data if first_node is not None else 0
        value += second_node.data if second_node is not None else 0
        carry = 1 if value >= 10 else 0
        value %= 10
        node = Node(value)
        node.next = self._add_reverse(
            first_node.next if first_node is not None else None,
            second_node.next if first_node is not None else None,
            carry)
        return node
